This invention relates to digital parallel processors or processor arrays of the type having a two dimensional matrix of substantially identical interconnected cells adapted to receive signals from other cells in the matrix to sequentially perform transformational operations on a plurality of input signals to produce an output based upon such operations. Thus, the output of any cell under consideration is dependent upon the results of operations performed by neighboring cells, which results are received as inputs by such a cell.
There are many examples of different types of parallel processors or processor arrays in the prior art. Over the years, in particular, dating back into the 1950's, many studies have been made by scientists and researchers concerning the properties of cell arrays and cell masses. Much of this research pertained to studies with intent on understanding and duplicating neuron activity of the human brain, particularly in connection with patterns of learning and recognition. See, for example, the articles of R. L. Beurle, "Properties of a Mass of Cells Capable of Regenerating Pulses", Royal Society of London Philosophical Transactions, Series B: Biological Sciences, Vol. 240 (B669) pp. 8-94 (1956); D. R. Smith et al, "Maintained Activity in Neural Nets", ACM, 1969; and G. M. Edelman et al, "Selective Networks Capable of Representative Transformations Limited Generalizations, and Associated Memory", Proceedings of National Academy of Science, U.S.A., Vol. 79, p.p. 2091-2095, March, 1982.
From these early studies, many new developments have arisen for parallel processing architecture and design wherein each cell structure in a processor cell array have their individual logic capability for processing data as well as limited memory or storage capacity. These developments were, in part, moved forward by the combination of (1) a need for processing, in a timely manner, a myriad of input data and (2) the advent of large scale integration (LSI) and, later, very large scale integration (VLSI). Examples in the literature of such developments are W. H. Kautz, "Cellular Logic-in-Memory Arrays", IEEE Transactions on Computers, pp. 1566-1569, December, 1971; and D. H. Lawrie, "Access & Alignment of Data in An Array Processor", IEEE Transactions on Computers, Vol. C-24, No. 12, pp. 1145-1155, December, 1975.
One of the most fundamentally referred to examples of a digital parallel processor in the patent literature is Unger U.S. Pat. No. 3,106,698 comprising a two dimensional matrix of identical processing elements or cells having a logic and storage capability. Each cell is connected to a plurality of neighboring cells and input data or signals may be introduced directly into each cell from an equivalent cell via an input array. Processing in each cell is accomplished under the control of a master control which issues general orders to all of the cells to permit simultaneous processing of the data in each cell and transfer information between cells through multiplexer links. A series of transformations are performed on the input data by the cells to arrive at an output matrix. Other examples of such parallel processor arrays under the control of a master control, such as a central processor or controller, are U.S. Pat. Nos. 4,065,808; 4,215,401; 4,270,169 and 4,395,699.
Some of the best known applications for parallel processors or processor arrays is automatic recognition, analization, digitization and/or classification of patterns, and the process of pictorial information or alphanumeric character type information. An example of such a processor is disclosed in U.S. Pat. No. 4,060,713 relating to analysis of images by comparison of values of image elements with neighboring image elements in a two dimensional processing field. U.S. Pat. No. 4,384,273 discloses an orthogonal array of interconnected array cells with time warping signal recognition for matching signal patterns. Another patent is above mentioned U.S. Pat. No. 4,395,699 relating to an image analyzer system having a processor array for analyzing groups of neighborhood pixel values and selectively transforming the pixel values as a result of such group analysis.
Today, parallel computation holds promises in many fields, ranging from numerical methods and robotics, to cognitive processes such as vision and speech understanding. Recent advances in VLSI technology have made it possible to construct concurrent processor arrays based on a regular array of locally connected elements or cells. Besides their useful applications, such processor arrays have the potential of exhibiting behavior characterized by self-organization, learning, and recognition.
Because of the large number of array cells and associated control means, these arrays are relatively complex in architecture and design. While prior processor arrays have aimed at simplifying these processors, it is a difficult task, particularly where accuracy is a paramount parameter and constraint desired in the processing operation carried out by the array cells.
We have discovered that a processor array may be designed to have a learning capability sufficient for utilization in the above-mentioned applications while not being constrained to a high degree of accuracy, i.e., providing an output immune to errors that may occur in the one or several individual cells of the array. We refer to this immunity as "self-repairing".